Count of Subset Sum
Let's solve the Count of Subset Sum problem using Dynamic Programming.
Statement#
Given a set of positive numbers nums and a value target_sum, count the total number of subsets of the given set whose sum is equal to the target_sum.
Let’s say you are given a set = and a target sum = . The output will be 2 as the following subsets:
- 4
will add up to make the desired sum.
Constraints:
-
nums.length -
target_sum -
nums[i]
Examples#
No. | nums | target_sum | Output |
1 | {1, 2, 3, 4} | 4 | 2 |
2 | {1, 2, 7, 4, 5} | 9 | 2 |
3 | {1, 2, 3, 7} | 6 | 1 |
Try it yourself#
Implement your solution in the following playground.
Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.
Hint: Use dynamic programming and see the magic.
Solution#
We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack Dynamic programming pattern.
Naive approach#
The naive approach is to find the possible combinations from the set, which makes up our target_sum. We know that we have to trace down all subsets. Therefore, we have to evaluate every element of the set.
For example, we have the following set of positive values given along with a target_sum of :
- set:
The subsets whose sum will be equal to the target_sum are:
We cannot do because we can consider each element only once.
So, we need a recursive solution to make all these calculations, as shown above. In other words, we will divide our problem into smaller subproblems, starting from the start of the nums list and for each element, we will do the following steps:
-
Check for the following base cases:
-
If the
target_sumis 0, it means that we can reach the sum of without including any element in our subset resulting in an empty subset, so we return1to include an empty subset. -
If we have traversed all of our elements then we cannot proceed further to calculate the required sum. So we return
0.
-
-
Consider the current element for the required sum.
- If it contributes to making up the
target_sum, we subtract thetarget_sumfrom the current number and proceed on to the next number with the new target sum oftarget_sum–nums[current_index].
- If it contributes to making up the
-
Do not consider the contribution of the current element for the
target_sumand move on to consider the rest of the numbers.
Let’s try to implement the algorithm as discussed above:
Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.
Time complexity#
The time complexity of the naive approach is , where is the total number of elements. This is because we have two possible choices every time, either to include the item or not.
Space complexity#
As the maximum depth of the recursive call tree is , and each call stores its data on the stack, the space complexity of this approach is .
Optimized solution using dynamic programming#
Now, let’s improve the recursive solution using top-down and bottom-up approaches.
Top-down solution#
The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in a table.
As we have to check each possible combination of all elements present in nums, we can store computed values and use them later whenever we need. For this, we will use a 2-D array to store the computed results at each step. Whenever we encounter a subproblem whose value is already calculated, we will simply fetch our already computed result instead of doing all the calculations again. This fetching takes place in time.
The 2-D array will be of size and initialized with to indicate that these subproblems are yet to be solved. The rows correspond to each element in the input array and the columns correspond to the remaining sums from to the target sum. So, for a given number and the remaining sum, we’ll do the following in the helper function:
-
Check the base cases as done in the naive approach.
-
If you look at the code shown below, you will see that we are checking if the count of subsets for a given element and the remaining sum has already been evaluated or not.
-
If it hasn’t already been evaluated, evaluate it as done in the naive approach and store the result in the 2-D array at
lookup_table[current_index][required_sum]. Thecurrent_indexspecifies the index of the current element in thenumsarray. -
If it has already been evaluated, fetch the computed result from
lookup_table[current_index][required_sum].
-
Let’s implement this algorithm:
Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.
Time complexity#
As we avoided redundant calculations by storing all the intermediate results in a 2-D array, the time complexity of this approach is reduced to , where is the number of elements and is the target sum.
Space complexity#
The space complexity of the top-down solution is , corresponding to the size of the 2-D array used to store intermediate values.
Bottom-up solution#
The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. A 2-D array of size , where is the input set size and is the target sum, which is used to store the results of subproblems. All the cells in the table are initialized to . In each iteration, we consider a number from the input set and check if that number can be included in our subset to reach the remaining sum. If you look at the code shown below, you will see the following steps to calculate the count of the subset sum:
-
Check the base case for the first number:
-
If the first number in the input array is , we update the cell at
lookup[0][0]to because the empty set and the set will both contribute to the zero sum. -
If the first number is not , we update the cell at
lookup[0][0]to because only the empty set will contribute to the zero sum. Also, if the number is less than the , it’ll contribute towards the , so update the cell atlookup[0][nums[0]]to .
-
-
We iterate the input array starting from the index, and for each of the numbers, we perform two steps for each
required_sumfrom to :-
Exclude the number. Get the count of all the subsets before the given number by fetching the value from
lookup[current-1][required_sum]. -
Include the number if its value is not more than the
required_sum. Get the count of all the subsets for the remaining target ofrequired_sum - nums[current]by fetching it fromlookup[current-1][required_sum - nums[current]]. -
Add the counts and store it in
lookup[current][required_sum].
-
-
After all the calculations,
lookup[nums_len - 1][target_sum]has the count of all the subsets having the sum equal to thetarget_sum.
Let’s see the illustration below to understand the algorithm.
Note: The cells in yellow are the current indexes being processed. The cells in purple are counts fetched from the previous iteration. The ind variable in the slides is the same as the
currentvariable used in the explanation/code.
1 of 18
2 of 18
3 of 18
4 of 18
5 of 18
6 of 18
7 of 18
8 of 18
9 of 18
10 of 18
11 of 18
12 of 18
13 of 18
14 of 18
15 of 18
16 of 18
17 of 18
18 of 18
Let’s implement the algorithm as discussed above:
Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.
Time complexity#
The time complexity of this approach is reduced to , where is the number of elements and is the target sum.
Space complexity#
We need space in memory to store the intermediate values.
Subset Sum
Partition Array Into Two Arrays to Minimize Sum Difference